High-level languages for document formatting exist in many forms, some of which accept as input a description of a document in the form of an input tree. An example of such an input tree is presented in FIG. 1. The input tree comprises two main types of elements, namely data elements and instruction elements, those elements in FIG. 1 being indicated in FIG. 2. The data elements contain data to be formatted. Each data element can include text or images. Instruction elements contain information used by a document formatter to arrange the data elements on pages when producing an output. As seen in FIG. 3, the data elements form leaf nodes in the tree whereas the instruction elements form nodes. Further, nodes A and B are child nodes of node Cat(2). The left node, Node A in the example, is defined as the first child of node Cat(2), whereas the right node, Node B, is defined as the second child node Cat(2).
Instruction elements can be thought of as operators that define the output positions of data elements. There are a number of instruction elements or operators available. Certain of the instruction elements, for example those defining text size, text spacing and the like, typically only have one child.
The other relevant instruction in FIGS. 1 to 3 is “Cat( )”, which performs vertical concatenation. Each concatenation instruction places its left parameter (the first child) above its right parameter (second child). For example, Cat(2) would place the content of data element B below the content of data element A.
As an input, data elements do not have an actual position. The actual position of the data elements is determined by the document formatter by evaluating the input tree. In the example of FIG. 1, the formatter, following the directions given by the instruction elements, determines that the result of the Cat(2) operator is placed above the result of the Cat(3) operator. The Cat(2) operator in turn places the content of data element A above data element 13, and the Cat(3) operator places the content of data element C above data element D. The result is that data element A, B, C and D are stacked in that order.
However, when the content of data elements are placed on a page in order to produce an output, it is sometimes found that the result is too big to fit onto one page. Therefore, placing the content data elements onto the page following the order specified, should the content of a next data element not fit into the space left on the present page, the remainder of the data elements are promoted to a next page. In the example presented in FIG. 1, if only the content of data elements A, B and C can fit onto page 1, then the content of data element D is promoted to page 2. The formatter also positions the data elements on the pages. The result of the evaluation of the input tree is shown in FIG. 4.
To better explain the above, a galley and a galley target need to be defined. A galley is a part of the input tree, whereas a galley target is a placeholder for a galley. The galley is therefore not evaluated at a position in the input tree but rather at the point where it is placed into the galley target. The galley target is a stretchable area on the output area with size 0 when no galley is targeted into it. When a galley is targeted into a galley target, the galley target stretches to accommodate for the incoming galley. The galley is unable to stretch infinitely though. There are restrictions on the maximum size of each galley target. Should it happen that the galley target reaches its maximum size before the galley is exhausted, a new galley target is found for the remainder of the content of the galley and the process of accommodating the remainder of the galley into the new target is continued.
Placing a galley into a series of galley targets involves splitting the input tree into fragments, each fragment filling its target. FIG. 5 shows another example of a galley in the form of an input tree 500. It is assumed that the galley in the example of FIG. 5 is targeted into a sequence of targets, with only data elements A and B fitting into the first galley target in the sequence by taking all the available space defined by the restrictions on the first galley target. The rest of the galley is promoted to the following galley target in the sequence.
FIGS. 6A and 6B show the result after a portion of the galley of FIG. 5 is placed into the sequence of galley targets. The original input tree 500 shown in FIG. 5 is split into the two tree fragments 510 and 520 respectively. The first fragment 510, shown in FIG. 6A, is placed into the first galley target. The remainder of the galley which now resides in the second tree fragment 520, shown in FIG. 6B, is waiting to be placed into the following galley targets. Thus, the original galley was split into two separate smaller trees.
The arrangement described above is used in batch text formatters which produce an output from an input tree. However, this arrangement suffers from the disadvantage that once the galley is split into smaller trees, it is hard to relate the fragmented trees back to their original galley tree. This is for example necessary whenever the order or contents of the data elements are changed, thus preventing interactive formatting.